
// 给定一棵二叉搜索树，请设计算法返回其中第k大的节点。

// 全局属性泛型接口
interface iGlobalThis<T> {
    k: T;
    res: T;
}
// 暴露接口
var kthLargest = function (globalThis: iGlobalThis<number>, root: TreeNode, k: number): number {
    // 将k赋值给全局作用域
    globalThis.k = k;
    // 深度优先遍历
    DFS(globalThis, root);
    // 返回结果
    return globalThis.res;
};
// 深度优先遍历
function DFS(globalThis: iGlobalThis<number>, root: TreeNode | null) {
    // 递归出口
    if (root == null || globalThis.k == 0) {
        return
    }
    // 中序遍历的反转，右子树->根节点->左子树
    DFS(globalThis, root.right);
    // 根节点操作，k值更新，检测是否达到目标
    globalThis.k--;
    if (globalThis.k === 0) {
        globalThis.res = root.val;
    }
    DFS(globalThis, root.left);
}

        // 这道题比较简单了，我们知道二叉搜索树的中序遍历为递增序列
        // 根据以上性质，易得二叉搜索树的中序遍历倒序为递减序列
        // 因此，求 “二叉搜索树第 k 大的节点” 可转化为求 “此树的中序遍历倒序的第 k 个节点”。
        // 因此为求第 k 个节点，需要实现以下三项工作 ：
        // 1、递归遍历时计数，统计当前节点的序号；
        // 2、递归到第 k 个节点时，应记录结果 resres ；
        // 3、当k为0，后续的遍历即失去意义，可以提前终止函数（即返回）。
        // 代码上书写也比较轻松，算是复习一下深度优先递归遍历的写法。
